/*
 * To change this template, choose Tools | Templates
 * and open the template in the editor.
 *
 *
 */

package CasosDePrueba;

import busquedaEstrella.NodoE;
import busquedaEstrella.SucesorE;
import gui.ExcepcionParada;
import java.util.ArrayList;
import java.util.List;
import javax.swing.JOptionPane;

/**
 *
 * COMENTARIOS IMPORTANTES:
 *
 * CUANDO COLOCAR UN NODO EN LA LISTA DE CERRADOS:
 * cuando se tuvo todos sus hijos.
 *
 * CUANDO MARCAR A UN NODO COMO CERRADO:
 * cuando se encuentre repetido al nodo en otro lugar y este nodo tenga
 * el valor de f mayor.
 *
 *
 */
public class busquedaEstrellaT {
    public List<NodoE> abiertos;
    //la longitud de abiertos es igual a la cantidad total de nodos generados
    public List<NodoE> cerrados;
    public NodoE inicial;
    public NodoE objetivo;
    //el valor de nivel del objetivo es el valor del nivel de la solucion
    boolean encontroSolucion;
    public long tiempoTotalBusqueda;
    int idPasado = 0;
    public busquedaEstrellaT(NodoE padre){

        this.inicial = padre;
        this.inicial.setIdPadre(padre.getIdPadre());
        this.inicial.setId(padre.getId());
        this.inicial.setG(padre.g);
        this.inicial.setNivel(padre.getNivel());
        this.abiertos = new ArrayList();
        this.cerrados = new ArrayList();
        this.objetivo = inicial;
        this.objetivo.setId(inicial.getId());
        this.objetivo.setIdPadre(inicial.getIdPadre());
        encontroSolucion = false;
        tiempoTotalBusqueda = 0;

    }

    public void buscarEstrella() throws ExcepcionParada{
    //ESTE METODO REALIZA LA BUSQUEDA HEURISTICA A*

        /*
         * ESTADOS POSIBLES EN LOS QUE PUEDE ESTAR UN NODO:
         *  EN ABIERTOS
         *  EN ABIERTOS PERO MARCADO COMO CERRADO (APARECE CON F MAYOR QUE EN OTRA PARTE)
         *  EN CERRADOS (TUVO TODOS SUS HIJOS)
         *
         *
         */
        //Aca comenzamos a contar el tiempo
        long tiempoInicio = System.currentTimeMillis();
        long totalTiempo = 0;

        this.cerrados.add(this.inicial);
        this.inicial.setCerrado(true);
        this.abiertos.add(this.inicial);


        boolean noFinal = true;
        boolean noEsMenor = true;

        NodoE estadoActual;
        estadoActual = this.inicial;
        estadoActual.setG(this.inicial.getG());
        estadoActual.setId(this.inicial.getId());
        estadoActual.setIdPadre(this.inicial.getIdPadre());
        estadoActual.setNivel(this.inicial.getNivel());
        estadoActual.mostrarValores();

        if(this.esEstadoFinal(this.inicial)){
            noFinal = false;

        }
        SucesorE tenerHijos = new SucesorE(estadoActual);
        idPasado = tenerHijos.obtenerHijos(idPasado);

        List<NodoE> hijos;

        

        hijos = tenerHijos.getHijos();

        for(int j=0;j<hijos.size();j++){

            this.abiertos.add(hijos.get(j));

        }

        //AHI ESTA EL PRIMER NIVEL

        while((noFinal)&&(noEsMenor)&&(totalTiempo<90000)){

            estadoActual = this.obtenerNodoMenorF();
            System.out.println("Nodo menor obtenido");
            estadoActual.mostrarValores();
            if(this.esEstadoFinal(estadoActual)){

                noFinal = false;
                noEsMenor = false;
                encontroSolucion = true;
                System.out.println("Termino la busqueda. Encontro solucion");
                this.setObjetivo(estadoActual);
                this.getObjetivo().setCerrado(estadoActual.isCerrado());
                this.getObjetivo().setF(estadoActual.getF());
                this.getObjetivo().setG(estadoActual.getG());
                this.getObjetivo().setId(estadoActual.getId());
                this.getObjetivo().setIdPadre(estadoActual.getIdPadre());
                this.getObjetivo().setNivel(estadoActual.getNivel());

            }else{
            
                //OBTENEMOS LOS SUCESORES DEL NODO Y LOS AGREGAMOS A ABIERTOS
                SucesorE obtenerLosHijos = new SucesorE(estadoActual);
                obtenerLosHijos.obtenerHijos(idPasado);
                this.cerrados.add(estadoActual);

                List<NodoE> hijosActuales;
                hijosActuales = obtenerLosHijos.getHijos();

                //AHORA TRATAMOS CADA HIJO ANTES DE COLOCAR EN ABIERTOS
                /*
                 * hay que recorrer abiertos para ver si aparece y comparar los costos
                 * el que tenga mayor costo, ese se marca como cerrado
                 */

                 for(int i=0;i<hijosActuales.size();i++){

                     NodoE hijoEnCurso;
                     hijoEnCurso = hijosActuales.get(i);
                     hijoEnCurso.setCerrado(hijosActuales.get(i).isCerrado());
                     hijoEnCurso.setF(hijosActuales.get(i).getF());
                     hijoEnCurso.setG(hijosActuales.get(i).getG());
                     hijoEnCurso.setId(hijosActuales.get(i).getId());
                     hijoEnCurso.setIdPadre(hijosActuales.get(i).getIdPadre());
                     hijoEnCurso.setNivel(hijosActuales.get(i).getNivel());

                     //ahora hay que buscar al nodo en abiertos
                     int [][] matrizHijoEnCurso;
                     matrizHijoEnCurso = hijoEnCurso.getPosicion();

                     for(int j=0;j<this.abiertos.size();j++){

                         int [][] matrizAux;
                         matrizAux = this.abiertos.get(j).getPosicion();

                         //ahora comparar
                         boolean distinto = false;
                         for(int k=0;k<8;k++){
                             for(int p=0;p<8;p++){
                                 if(matrizHijoEnCurso[k][p]!=matrizAux[k][p]){
                                     distinto = true;
                                 }
                             }
                         }

                         if(distinto){

                         }else{
                             //COMPARAR LOS F
                             int menor = this.compararF(hijoEnCurso, this.abiertos.get(j));
                             if(menor == 1){
                                this.marcarNodoComoCerrado(this.abiertos.get(j).getId(), this.abiertos.get(j).getNivel());
                             }else{
                                 hijoEnCurso.setCerrado(true);
                             }

                         }


                     }
                     hijoEnCurso.mostrarValores();                   
                     System.out.println("Agregamos el nodo a abiertos");

                     if(this.esEstadoFinal(hijoEnCurso)){
                        System.out.println("Encontro solución");
                         this.abiertos.add(hijoEnCurso);
                         this.setObjetivo(hijoEnCurso);
                         this.getObjetivo().setCerrado(hijoEnCurso.isCerrado());
                         this.getObjetivo().setF(hijoEnCurso.getF());
                         this.getObjetivo().setG(hijoEnCurso.getG());
                         this.getObjetivo().setId(hijoEnCurso.getId());
                         this.getObjetivo().setIdPadre(hijoEnCurso.getIdPadre());
                         this.getObjetivo().setNivel(hijoEnCurso.getNivel());
                         noFinal = false;
                         encontroSolucion = true;
                         break;
                     }

                     this.abiertos.add(hijoEnCurso);
                     //Aca recalculamos el tiempo
                    totalTiempo = System.currentTimeMillis() - tiempoInicio;
                    this.setTiempoTotalBusqueda(totalTiempo);
                    if(totalTiempo>=90000){
                        /*
                        int seleccion = JOptionPane.showConfirmDialog(null, "La búsqueda ha tardado demasiado ¿Desea continuar?",null, JOptionPane.YES_NO_OPTION);
                     if(seleccion == 0){
                         System.out.println("************************************************************");

                     }else{
                         //this.interrupt();
                    JOptionPane.showMessageDialog(null,"La búsqueda ha sido detenida");
                   
                         * 
                         */
                         throw new ExcepcionParada("La busqueda tardo demasiado en encontrar una solución");
/*

                     }
                         * 
                         */

                    }
                 }







            }


        

        }

       
    }

    public boolean esEstadoFinal(NodoE estadoActual){

        boolean es = false;

        boolean noTiene1 = false;
        int [][] valores;
        valores = new int[8][8];
        valores = estadoActual.getPosicion();
        int cant1 = 0;
        for(int i=0;i<8;i++){
            for(int j=0;j<8;j++){
                if(valores[i][j]==1){
                    cant1++;
                }
            }
        }

        if(cant1==0){
            noTiene1 = true;


            es = true;
        }

        //
        if(noTiene1){

            
            int costoMenor = this.abiertos.get(0).getF();
            for(int k=0;k<this.abiertos.size();k++){

                if(this.abiertos.get(k).getF()<costoMenor){

                    costoMenor = this.abiertos.get(k).getF();

                }

            }

            if(estadoActual.getF()<=costoMenor){
                es = true;
            }
             
             

        }
         
         


        
        return es;
    }

    public NodoE obtenerNodoMenorF(){


        NodoE aDevolver;
        int ultimo;
        ultimo = this.abiertos.size() - 1;
        aDevolver = this.abiertos.get(ultimo);
        aDevolver.setF(this.abiertos.get(ultimo).getF());
        aDevolver.setG(this.abiertos.get(ultimo).getG());
        aDevolver.setId(this.abiertos.get(ultimo).getId());
        aDevolver.setIdPadre(this.abiertos.get(ultimo).getIdPadre());
        aDevolver.setCerrado(this.abiertos.get(ultimo).isCerrado());
        aDevolver.setNivel(this.abiertos.get(ultimo).getNivel());

        for(int i=0;i<this.abiertos.size();i++){
        
            NodoE aux;
            aux = this.abiertos.get(i);
            aux.setF(this.abiertos.get(i).getF());
            aux.setG(this.abiertos.get(i).getG());
            aux.setId(this.abiertos.get(i).getId());
            aux.setIdPadre(this.abiertos.get(i).getIdPadre());
            aux.setCerrado(this.abiertos.get(i).isCerrado());
            aux.setNivel(this.abiertos.get(i).getNivel());

            if((aux.isCerrado() == false)&&(aux.getF()<=aDevolver.getF())&&(!this.EstaEnCerrados(aux))&&(!this.perteneceAunaRamaCerrada(aux))){
                //ES EL NODO DE MENOR COSTO QUE NO ESTA CERRADO
                //ES EL QUE HAY QUE DEVOLVER
                aDevolver = this.abiertos.get(i);
                aDevolver.setF(this.abiertos.get(i).getF());
                aDevolver.setG(this.abiertos.get(i).getG());
                aDevolver.setId(this.abiertos.get(i).getId());
                aDevolver.setIdPadre(this.abiertos.get(i).getIdPadre());
                aDevolver.setCerrado(this.abiertos.get(i).isCerrado());
                aDevolver.setNivel(this.abiertos.get(i).getNivel());
                
            }
            
        }



        return aDevolver;

    }

    public boolean EstaEnCerrados(NodoE buscar){

        boolean esta = false;

        for(int i=0;i<this.cerrados.size();i++){

            NodoE actual;
            actual = this.cerrados.get(i);

            int [][] buscarMatriz;
            int [][] actualMatriz;

            buscarMatriz = buscar.getPosicion();
            actualMatriz = actual.getPosicion();

            //comparamos las dos matrices
            boolean distinto = false;
            for(int a=0;a<8;a++){
                for(int b=0;b<8;b++){

                    if(buscarMatriz[a][b]!=actualMatriz[a][b]){
                        distinto = true;
                    }
                }
            }
            if(distinto){

            }else{
                //SE ENCONTRO EL ESTADO EN CERRADOS
                esta = true;
                System.out.println("Encontrado en cerrados");
                break;
            }

        }
System.out.println("Sali del bucle");
        return esta;

    }

    public boolean perteneceAunaRamaCerrada(NodoE nodo){

        boolean pertenece = false;

        int idNodoPadre;
        idNodoPadre = nodo.getIdPadre();
        int nivelBusqueda;
        nivelBusqueda = nodo.getNivel() - 1;

        while(nivelBusqueda>0){
        
             int tamaño = this.abiertos.size() - 1;
             for(int i=tamaño; i>0;i--){

                 boolean salir = false;
                 if((this.abiertos.get(i).getId()==idNodoPadre)&&(this.abiertos.get(i).getNivel()==nivelBusqueda)){
                    salir = true;
                     if(this.abiertos.get(i).isCerrado()){

                         pertenece = true;

                     }else{

                         idNodoPadre = this.abiertos.get(i).getIdPadre();
                         nivelBusqueda = nivelBusqueda - 1;

                     }


                 }
                 if(salir){
                     break;
                 }

             }

             if(pertenece){
                 System.out.println("Pertenece a una rama cerrada");
                 break;
             }

        }

        return pertenece;

    }

    public int compararF(NodoE primero, NodoE segundo){
        /*
         * ESTE METODO COMPARA LOS F Y DEVUELVE CUAL DE LOS 2 ES MENOR
         */
        int num = 0;
        if(primero.getF()<=segundo.getF()){

            num = 1;

        }else{
            num = 2;
        }

        return num;



    }

    public void marcarNodoComoCerrado(int id, int nivel){
        /*
         * ESTE METODO BUSCA EL NODO CON LOS VALORES PASADOS Y LOS CIERRA
         */
        for(int i=0;i<this.abiertos.size();i++){

            if((this.abiertos.get(i).getId()==id)&&(this.abiertos.get(i).getNivel()==nivel)){
                this.abiertos.get(i).setCerrado(true);
                System.out.println("El nodo ha sido marcado como cerrado");
                break;
            }
        }
    }

    public List<NodoE> devolverCamino(){

        List<NodoE> caminoRecorrido;
        caminoRecorrido = new ArrayList();
        caminoRecorrido.add(this.getObjetivo());
        int nivelCamino;
        int idPadreNivel;
        nivelCamino = this.getObjetivo().getNivel() - 1;
        System.out.println(nivelCamino);
        idPadreNivel = this.getObjetivo().getIdPadre();

        while(nivelCamino>0){
        System.out.println(nivelCamino);
            for(int i=this.abiertos.size()-1; i>0;i--){
                NodoE elm;
                elm = this.abiertos.get(i);
                elm.setId(this.abiertos.get(i).getId());
                elm.setIdPadre(this.abiertos.get(i).getIdPadre());
                elm.setNivel(this.abiertos.get(i).getNivel());
                if((elm.getId()==idPadreNivel)&&(elm.getNivel()==nivelCamino)){

                    caminoRecorrido.add(elm);
                    idPadreNivel = elm.getIdPadre();
                    nivelCamino = nivelCamino - 1;
                    
                }

            }
        
            caminoRecorrido.add(this.inicial);

        }

        System.out.println("Recorrido del algoritmo a estrella");
        System.out.println(this.abiertos.size());
        System.out.println(caminoRecorrido.size());
        for(int j=caminoRecorrido.size()-1;j>=0;j--){
            NodoE elm = caminoRecorrido.get(j);
            int [][] matriz;
            matriz = elm.getPosicion();
            for(int k=0;k<8;k++){
                for(int p=0;p<8;p++){

                    System.out.print(matriz[k][p]);

                }
                System.out.println();
            }
            System.out.println();
        }

        System.out.println("Termino");
        
        return caminoRecorrido;


    }
    /**
     * @return the abiertos
     */
    public List<NodoE> getAbiertos() {
        return abiertos;
    }

    /**
     * @param abiertos the abiertos to set
     */
    public void setAbiertos(List<NodoE> abiertos) {
        this.abiertos = abiertos;
    }

    /**
     * @return the cerrados
     */
    public List<NodoE> getCerrados() {
        return cerrados;
    }

    /**
     * @param cerrados the cerrados to set
     */
    public void setCerrados(List<NodoE> cerrados) {
        this.cerrados = cerrados;
    }

    /**
     * @return the inicial
     */
    public NodoE getInicial() {
        return inicial;
    }

    /**
     * @param inicial the inicial to set
     */
    public void setInicial(NodoE inicial) {
        this.inicial = inicial;
    }

    //metodo que obtiene la profundidad maxima alcanzada
    public int profundidadMaximaAlcanzada(){

        int profundidadMaxima;
        profundidadMaxima = 0;

        for(int i=0;i<this.abiertos.size();i++){

            if(this.abiertos.get(i).getNivel()>profundidadMaxima){
                profundidadMaxima = this.abiertos.get(i).getNivel();
            }

        }

        return profundidadMaxima;



    }

    /**
     * @return the tiempoTotalBusqueda
     */
    public long getTiempoTotalBusqueda() {
        return tiempoTotalBusqueda;
    }

    /**
     * @param tiempoTotalBusqueda the tiempoTotalBusqueda to set
     */
    public void setTiempoTotalBusqueda(long tiempoTotalBusqueda) {
        this.tiempoTotalBusqueda = tiempoTotalBusqueda;
    }

    /**
     * @return the objetivo
     */
    public NodoE getObjetivo() {
        return objetivo;
    }

    /**
     * @param objetivo the objetivo to set
     */
    public void setObjetivo(NodoE objetivo) {
        this.objetivo = objetivo;
    }

    
}
